package jzoffer;

import leetcode.tree.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author MaoLin Wang
 * @date 2020/10/12 9:29 上午
 */
public class _37序列化二叉树 {
    public static String serialize(TreeNode root) {
        if (root==null){
            return "[]";
        }
        StringBuilder sb=new StringBuilder();
        sb.append("[");
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            if (null==node){
                sb.append("null").append(",");
            }else {
                sb.append(node.val).append(",");
                queue.offer(node.left);
                queue.offer(node.right);
            }
        }
        sb.deleteCharAt(sb.length()-1).append("]");
        return sb.toString();

    }

    // Decodes your encoded data to tree.
    public static TreeNode deserialize(String data) {
        if (data==null || data.length()==2){
            return null;
        }
        if (data.indexOf(",")==-1){
            return new TreeNode(data.charAt(1));
        }
        String[] vals = data.substring(1, data.length() - 1).split(",");
        TreeNode root=new TreeNode(Integer.parseInt(vals[0]));
        Queue<TreeNode>queue=new LinkedList<>();
        queue.offer(root);
        int i=1;
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            if (!vals[i].equals("null")){
                node.left=new TreeNode(Integer.parseInt(vals[i]));
                queue.offer(node.left);
            }
            i++;
            if (!vals[i].equals("null")){
                node.right=new TreeNode(Integer.parseInt(vals[i]));
                queue.offer(node.right);
            }
        }
        return root;
    }





    public static void main(String[] args) {
        System.out.println("null]".substring(0,"null]".length()-1));
        TreeNode treeNode=new TreeNode(5);
        treeNode.left=new TreeNode(2);
        treeNode.right=new TreeNode(3);
        treeNode.right.left=new TreeNode(2);
        treeNode.right.right=new TreeNode(4);
        treeNode.right.left.left=new TreeNode(3);
        treeNode.right.left.right=new TreeNode(1);
        String serialize = serialize(treeNode);
        System.out.println(serialize);
        TreeNode deserialize = deserialize(serialize);
        deserialize.preOrder();

    }
}
